package C057;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: c02
 * Package: C057
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/4/27 22:45
 * @Version 1.0
 * @Since 1.0
 */
public class c02 {
    public static void main(String[] args) {
        //int[][] arr = {{1, 2, 5}, {2, 3, 8}, {1, 5, 10}};
        int[][] arr = {{5, 1, 4}, {0, 4, 18}};
        System.out.println(findAllPeople(11, arr, 1));
    }

    static int MAXLEN = 100001;
    static int[] stack = new int[MAXLEN];
    static int[] father = new int[MAXLEN];
    static int[] statck = new int[MAXLEN];
    static boolean[] secret = new boolean[MAXLEN];
    int size, m;

    public static List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        int m = meetings.length;
        // 排序
        Arrays.sort(meetings, (int[] arr1, int[] arr2) -> {
            return arr1[2] - arr2[2];
        });
        build(n, firstPerson);
        union(0, firstPerson);

        for (int l = 0, r = 0; l < m; ) {
            r = l;
            while (r + 1 < m && meetings[r][2] == meetings[r + 1][2]) {
                r++;
            }

            // l ... r 的时间是一样的, 统一时刻的会议
            for (int i = l; i <= r; i++) {
                union(meetings[i][0], meetings[i][1]);
            }

            // 归为不知道秘密的并查集
            for (; l <= r; l++) {
                if (!secret[find(meetings[l][0])]) {
                    father[meetings[l][0]] = meetings[l][0];
                }
                if (!secret[find(meetings[l][1])]) {
                    father[meetings[l][1]] = meetings[l][1];
                }
            }
        }
        // 返回结果
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (secret[find(i)]) {
                res.add(i);
            }
        }
        return res;
    }

    private static void union(int i, int j) {
        int fatheri = find(i);
        int fatherj = find(j);
        if (fatherj == fatheri) {
            return;
        }
        father[fatherj] = fatheri;
        secret[fatheri] |= secret[fatherj];
    }

    private static int find(int i) {
        int size = 0;
        while (father[i] != i) {
            statck[size++] = i;
            i = father[i];
        }

        // 扁平化
        while (size > 0) {
            father[statck[--size]] = i;
        }
        return i;
    }

    private static void build(int n, int firstPerson) {
        Arrays.fill(secret, false);
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        secret[0] = secret[firstPerson] = true;
    }
}
